class node():
    def __init__(self,val=None,parent=None):
        self.key=val
        self.left=None
        self.right=None
        self.parent=parent
    def insert(self,val):
        if val<self.key:
            if self.left is None:
                self.left=node(val,self)
            else:
                self.left.insert(val)
        else:
            if self.right is None:
                self.right=node(val,self)
            else:
                self.right.insert(val)
    def minimum(self):
        current=self
        while current.left is not None:
            current=current.left
        return current
    def successor(self):
        if self.right is not None:
            return self.right.minimum()
        current=self
        while current.parent is not None and current.parent.right is current:
            current=current.parent #left up
        return current.parent #one right up

class binTree():
    def __init__(self):
        self.root=None
    def insert(self,val):
        if self.root is None:
            self.root=node(val)#equal to node(val,None)
        else:
            self.root.insert(val)
    def printall(self):
        if self.root is None:
            print 'Empty binTree'
        else:
            current=self.root.minimum()
            print current.key,
            while current.successor() is not None:
                current=current.successor()
                print current.key, 

if __name__=='__main__':
    import random
    tree=binTree()
    for i in random.sample(xrange(50),20):
        tree.insert(i)
    tree.printall()
